package leetcode.problems;

import java.util.HashMap;
import java.util.Map;

/**
 * Split Array into Consecutive Subsequences
 * 将数组拆分为连续的子序列
 * Created by gmwang on 2018/3/23
 */
public class _0323SplitArrayintoConsecutiveSubsequences {
    /**
     * You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.
     * <p>
     * Example 1:
     * Input: [1,2,3,3,4,5]
     * Output: True
     * Explanation:
     * You can split them into two consecutive subsequences :
     * 1, 2, 3
     * 3, 4, 5
     * Example 2:
     * Input: [1,2,3,3,4,4,5,5]
     * Output: True
     * Explanation:
     * You can split them into two consecutive subsequences :
     * 1, 2, 3, 4, 5
     * 3, 4, 5
     * Example 3:
     * Input: [1,2,3,4,4,5]
     * Output: False
     * Note:
     * The length of the input is in range of [1, 10000]
     * <p>
     * <p>
     * 给定一个整数数组按照升序排列（可能包含重复项），您需要将它们分成几个子序列，其中每个子序列至少包含3个连续的整数。返回你是否可以进行这样的分割。
     * <p>
     * 例1：
     * 输入： [1,2,3,3,4,5]
     * 输出：true
     * 说明：
     * 可以将它们分成两个连续的子序列：
     * 1，2，3
     * 3，4，5
     * 例2：
     * 输入： [1,2,3,3,4,4,5,5]
     * 输出：true
     * 说明：
     * 可以将它们分成两个连续的子序列：
     * 1，2，3，4，5
     * 3，4，5
     * 例3：
     * 输入： [1,2,3,4,4,5]
     * 输出：false
     * 注意：
     * 输入的长度范围为[1，10000]
     */
    /**
     * 思路：
     * 找出所有连续的序列，判断个数是否都大于3
     *
     * @param nums
     * @return
     */
//    public static boolean isPossible(int[] nums) {
//        Boolean flag = false;
//        int sequences = 0;
////        int [] numsSequence = new int[nums.length];
//        for (int i = 0; i < nums.length; i++) {
//            //如果前者大于后者1，则为连续
//            if (i == 0 || nums[i] - nums[i - 1] == 1) {
//                sequences += 1;
//            } else {
//                sequences = 1;
//            }
//        }
//        if (sequences > 2) flag = true;
//        return flag;
//    }
    public static boolean isPossible(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>(), appendfreq = new HashMap<>();
        for (int i : nums) {
            //getOrDefault  key包含i,就返回i对应的值，否则返回0
            freq.put(i, freq.getOrDefault(i, 0) + 1);
        }
        for (int i : nums) {
            if (freq.get(i) == 0) continue;
            else if (appendfreq.getOrDefault(i, 0) > 0) {
                appendfreq.put(i, appendfreq.get(i) - 1);
                appendfreq.put(i + 1, appendfreq.getOrDefault(i + 1, 0) + 1);
            }
            else if (freq.getOrDefault(i + 1, 0) > 0 && freq.getOrDefault(i + 2, 0) > 0) {
                freq.put(i + 1, freq.get(i + 1) - 1);
                freq.put(i + 2, freq.get(i + 2) - 1);
                appendfreq.put(i + 3, appendfreq.getOrDefault(i + 3, 0) + 1);
            } else return false;
            freq.put(i, freq.get(i) - 1);
        }
        return true;
    }

    public static void main(String[] args) {
//        int [] s = {1,2,3,3,4,5};
        int[] s = {1, 2, 3, 3, 4, 4, 5, 5};
        System.out.println(isPossible(s));
    }
}
